package com.tgy.algorithm._经典题目01;

public class _034_字符串切回文串 {


    public static int minPim(String content) {

        if (content == null || content.length() == 0) {
            return 0;
        }

        int len = content.length();
        char[] chars = content.toCharArray();

        boolean[][] cache = new boolean[len][len];

        // [L,R]
        for (int i = 0; i < len; i++) {
            // 中线
            cache[i][i] = true;
            // 中线偏右
            if (i < len - 1) {
                cache[i][i+1] = (chars[i] == chars[i+1]);
            }
        }

        /**
         * L 从底部开始
         * [L,R] 是 回文，则 chars[L] == chars[R] && cache[L + 1][R - 1] 为true
         */

        for (int i = len - 3; i >= 0; i--) {
            for (int j = i + 2; j < len; j++) {
                cache[i][j] = (chars[i] == chars[j]) && cache[i+1][j - 1];
            }
        }

//        System.out.println(cache);
        return doMinPin(chars,0,cache);
    }

    public static int doMinPin(char[] chars,int start,boolean[][] cache) {

        int len = chars.length;

        if (start >= len) {
            return 0;
        }
        int ret = chars.length;
        for (int i = start; i < len; i++) {
            if (cache[start][i]) {
                ret = Math.min(ret,doMinPin(chars,i+1,cache) + 1);
            }
        }

        return ret;
    }

    public static int minPin01(String content) {

        if (content == null || content.length() == 0) {
            return 0;
        }

        int len = content.length();
        char[] chars = content.toCharArray();

        boolean[][] cache = new boolean[len][len];

        // [L,R]
        for (int i = 0; i < len; i++) {
            // 中线
            cache[i][i] = true;
            // 中线偏右
            if (i < len - 1) {
                cache[i][i+1] = (chars[i] == chars[i+1]);
            }
        }

        /**
         * L 从底部开始
         * [L,R] 是 回文，则 chars[L] == chars[R] && cache[L + 1][R - 1] 为true
         */

        for (int i = len - 3; i >= 0; i--) {
            for (int j = i + 2; j < len; j++) {
                cache[i][j] = (chars[i] == chars[j]) && cache[i+1][j - 1];
            }
        }

        int[] dp = new int[len + 1];
        for (int i = 0; i < len; i++) {
            dp[i] = len;
        }

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len ; j++) {
                if (cache[i][j]) {
                    dp[i] = Math.min(dp[i],dp[j+1] + 1);
                }
            }
        }

        return dp[0];
    }

    public static void main(String[] args) {
        String content = "abacdc";
//        int i = minPim(content);
        int i = minPin01(content);
        System.out.println(i);
    }
}
